package heap;

/**
 * description:
 * author:张腾
 * date:2021-04-06
 */

/**
 * 堆  使用数组实现  是一颗完全二叉树
 * 一个节点a[k]的两个子节点分别为a[2k]，a[2k+1]
 * 每个节点的值都大于或等于其左右子节点的值，叫做大根堆
 * 每个节点的值都小于或等于其左右子节点的值，叫做小根堆（代码未实现）
 * @param <T>
 *
 * 堆是为了实现排序而设计的一种数据结构，它不是面向查找操作的，因而在堆中查找一个结点需要进行遍历，其平均时间复杂度是O(n)
 */
public class Heap<T extends Comparable<T>> {
    //存储堆中的元素
    private T[] items;
    //记录堆中元素的个数
    private int N;

    public Heap(int capacity){
        this.items = (T[]) new Comparable[capacity+1];  //0位置不存放
        this.N = 0;
    }

    //判断索引i处的元素是否小于索引j处的元素
    private boolean less(int i,int j){
        return items[i].compareTo(items[j])<0;
    }

    //交换堆中索引i和j处的值
    private void exch(int i,int j){
        T temp = items[i];
        items[i] = items[j];
        items[j] = temp;
    }

    //插入一个元素
    public void insert(T t){
        items[++N] = t;
        swim(N);
    }

    //使用上浮算法，使索引k处的元素在堆中处于一个正确的位置
    private void swim(int k){
        //不断比较当前节点的值和父节点的值，如果父节点小则交换位置，保证堆的有序性
        while (k>1){

            if (less(k/2,k)){
                exch(k/2,k);
            }else {
                break;
            }
            k = k/2;
        }
    }

    //删除堆中最大的元素，并返回这个元素
    public T delMax(){
        T max = items[1];
        //交换索引1处的元素和最大索引的元素，让完全二叉树最右侧的元素变为临时根节点
        exch(1,N);
        //删除最大索引处的元素，即原堆中最大的元素
        items[N] = null;
        N--;
        //使用下沉算法调整堆，让堆重新有序
        sink(1);
        return max;
    }

    //使用下沉算法，使索引k处的元素在堆中处于一个正确的位置
    private void sink(int k){
        //通过循环，不断比较当前 k节点 和 其左右子节点中的较大值的元素，如果当前元素小，则需交换位置
        while(2*k<=N){
            //获取当前节点的两个子节点中的较大值,赋值给max
            int max;
            if (2*k+1<=N){
                if (less(2*k,2*k+1)){
                    max = 2*k+1;
                }else{
                    max = 2*k;
                }
            }else {
                max = 2*k;
            }

            if (!less(k,max)){
                break;
            }
            //k小于max，则交换它们的值，再变换k继续往下沉
            exch(k,max);
            k=max;
        }

    }
}
